package fundamentals.unionfind;

public class WeightedQuickUnionFind {

    private int[] id;//分量id(以触点作为索引)
    private int[] sz;//根节点所对应的分量的大小
    private int count;//分量数量

    //
    /**
     * 初始化N个结点
     * @param N
     */
    public WeightedQuickUnionFind(int N){
        count=N;
        id=new int[N];
        sz=new int[N];
        for (int i = 0; i < N; i++) {
            id[i]=i;
            sz[i]=1;
        }
    }

    /**
     * 在p和q之间添加一条连接
     * @param p
     * @param q
     */
    public void union(int p,int q){
        int proot=find(p);
        int qroot=find(q);
        if(proot==qroot)return;
        if(sz[proot]<sz[qroot]){id[proot]=qroot;sz[qroot]+=sz[proot];}
        else {id[qroot]=proot;sz[proot]+=sz[qroot];}
        count--;

    }

    /**
     * p所在分量的标识符
     * @param p
     * @return
     */
    public int find(int p){
        while (p!=id[p])p=id[p];
        return p;
    }

    /**
     * 如果p和q在同一个分量中，则返回true
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p,int q){

        return find(p)==find(q);
    }

    public int getCount(){
        return count;
    }



}
